/* 利用动态规划的解题思路：
    DP[i][j] = 1 表示 字符串S[i...j]为不重复的字符串
    DP[i][j]为1的条件是DP[i+1][j-1]不为0,且S[i] != S[j] ,且S[i],S[j]不包含于 S[i+1 ... j-1]
    边界条件DP[i][j] = 1 (i == j)
    if ((DP[i+1][j-1] == 0) || (S[i] == S[j])) {
        DP[i][j] = 0
    } else {
        flag = 0
        // 遍历是否包含S[i],S[j]
        for(idx = i+1; idx <= j-1; idx++) {
            if (S[i] == S[idx] || S[j] == S[idx]) {
                flag = 1;
                break;
            }
        }
        if (flag == 0) {
            // 满足条件
            DP[i][j] = 1;
        } else {
            // 不满足条件
            DP[i][j] = 0;
        }
    }
这种解题思路会超时，因为递归方程里面又包含遍历，不理想是错误的解题思路
*/
#define MAX 5000
int DP[MAX][MAX];
int lengthOfLongestSubstring(char *s)
{
    int len = strlen(s);
    int i;
    int j;
    int idx;
    int maxlen = 1;
    int flag;
    if (len == 0)
    {
        return 0;
    }
    memset(DP, 0, sizeof(DP));
    // 初始化DP边界
    for (i = 0; i < len; i++)
    {
        DP[i][i] = 1;
    }

    for (j = 1; j < len; j++)
    {
        for (i = j - 1; i >= 0; i--)
        {
            /* 最小的基准值‘ab’ */
            if (j - i == 1)
            {
                /* 例如 'aa' */
                if (s[i] == s[j])
                {
                    DP[i][j] = 0;
                }
                /* 例如 'ab' */
                else
                {
                    DP[i][j] = 1;
                }
            }
            else if ((DP[i + 1][j - 1]) == 0 || (s[i] == s[j]) || (s[i] == s[i + 1]) || (s[i + 1] == s[j]))
            {
                /* 判断是否为非重复子串 */
                DP[i][j] = 0;
            }
            else
            {
                flag = 1;
                // 判断是否包含重复字符
                for (idx = i + 1; idx <= j - 1; idx++)
                {
                    if (s[idx] == s[i] || s[idx] == s[j])
                    {
                        flag = 0;
                        break;
                    }
                }
                if (flag == 0)
                {
                    DP[i][j] = 0;
                }
                else
                {
                    DP[i][j] = 1;
                }
            }
            /* 计算最大长度的不重复的子串 */
            if (DP[i][j] == 1)
            {
                if (maxlen < j - i + 1)
                {
                    maxlen = j - i + 1;
                }
            }
        }
    }

    return maxlen;
}